/*
    This file is part of VK/KittenPHP-DB-Engine.

    VK/KittenPHP-DB-Engine is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 2 of the License, or
    (at your option) any later version.

    VK/KittenPHP-DB-Engine is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with VK/KittenPHP-DB-Engine.  If not, see <http://www.gnu.org/licenses/>.

    This program is released under the GPL with the additional exemption 
    that compiling, linking, and/or using OpenSSL is allowed.
    You are free to remove this exemption from derived works.

    Copyright 2011-2012 Vkontakte Ltd
                   2011 Vitaliy Valtman
              2011-2012 Anton Maydell
*/

#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <stdarg.h>
#include <sys/resource.h>
#include "utils.h"
#include "stemmer-new.h"
#include "word-split.h"
#include "crc32.h"

#define MAX_ZALLOC 16380

//#define DEBUG_ZZMALLOC

double get_rusage_time (void) {
  struct rusage r;
  if (getrusage (RUSAGE_SELF, &r)) { return 0.0; }
  return r.ru_utime.tv_sec + r.ru_stime.tv_sec + 1e-6 * (r.ru_utime.tv_usec + r.ru_stime.tv_usec);
}

/**
  Returns i-th set bit position (integer from 0 to 31 inclusive) in given mask.
*/
int get_ith_setbit(int mask, int i) {
  int tmp1, tmp2;
  assert(i >= 0 && i < 32);
  while (i-- > 0) {
    mask &= mask-1;
  }
  assert(mask);
  asm("bsf %1,%0\n\t"
        :   "=&q"(tmp1), "=&q"(tmp2)
        :   "1"(mask)
        :   "cc");
  return tmp1;
}

int get_bitno_sparse(int mask, int i) {
  int j, m = 1 << i;
  if (0 == (mask & m) ) return -1;
  for (j = 0;;j++) {
    int w = mask & (mask - 1);
    if (m == (w ^ mask)) return j;
    mask = w;
  }
}

inline int popcount_short (int x) {
  /* generated by python code */
  static const char table[256] = {
    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8};
  assert ( ! (x >> 16) );
  return table[x >> 8] + table[x & 0xff];
}

/* mask should be in [0, 0xffff] */
int get_bitno(int mask, int i) {
  if (0 == (mask & (1<<i)) ) return -1;
  return popcount_short (mask & ((1 << i) - 1));
}

long long total_memory_used = 0;

#ifdef DEBUG_ZZMALLOC
long long size_sum_zzmallocs = 0;
long long size_sum_zzfree = 0;
long long tot_calls_zzmallocs = 0;
long long tot_calls_zzfree = 0;
#endif

long long get_malloc_memory_used (void) { return total_memory_used; }

void zzcheck_memory_leaks (void) {
  #ifdef DEBUG_ZZMALLOC
  if (size_sum_zzmallocs != size_sum_zzfree ||
      tot_calls_zzmallocs != tot_calls_zzfree) {
    fprintf (stderr, "size_sum_zzmallocs = %lld\n"
                     "size_sum_zzfree = %lld\n"
                     "tot_calls_zzmallocs = %lld\n"
                     "tot_calls_zzfree = %lld\n",
                     size_sum_zzmallocs, size_sum_zzfree,
                     tot_calls_zzmallocs, tot_calls_zzfree);
    assert (0);
    }
  #endif
}

void *zzmalloc (int size) {
  #ifdef DEBUG_ZZMALLOC
  size_sum_zzmallocs += size;
  tot_calls_zzmallocs++;
  #endif
  if (size < MAX_ZALLOC) {
    return zmalloc (size);
  } else {
    total_memory_used += size;
    return malloc (size);
  }
}

void *zzmalloc0 (int size) {
  #ifdef DEBUG_ZZMALLOC
  size_sum_zzmallocs += size;
  tot_calls_zzmallocs++;
  #endif
  if (size < MAX_ZALLOC) {
    return zmalloc0 (size);
  } else {
    total_memory_used += size;
    return calloc (size, 1);
  }
}

void zzfree (void *src, int size) {
  if (!src) { return; }
  #ifdef DEBUG_ZZMALLOC
  size_sum_zzfree += size;
  tot_calls_zzfree++;
  #endif
  if (size < MAX_ZALLOC) {
    zfree (src, size);
  } else {
    total_memory_used -= size;
    free (src);
  }
}

void *zzrealloc (void *p, int old_len, int new_len) {
  void *tmp = zzmalloc (new_len);
  if (!tmp) {
    return 0;
  }
  int t = old_len;
  if (old_len > new_len) {
    t = old_len;
  }
  memcpy (tmp, p, t);
  if (p) {
    zzfree (p, old_len);
  }
  return tmp;
}

void *zzrealloc_ushort_mask (void *src, int mask_old, int mask_new, int size_of_element) {
  if (!mask_new) {
    if (src) { zzfree (src, popcount_short (mask_old) * size_of_element); }
    return 0;
  }
  void *dst = zzmalloc0 ( popcount_short (mask_new) * size_of_element);
  if (!dst) { return 0; }
  if (src) {
    int psrc = 0, pdst = 0, u = mask_old | mask_new;
    while (u) {
      int x;
      u ^= x = u & -u; /* x := mask with lowest one bit */
      if (x & mask_new) {
        if (x & mask_old) {
          memcpy (dst + pdst, src + psrc, size_of_element);
          psrc += size_of_element;
        }
        pdst += size_of_element;
      } else {
        psrc += size_of_element;
      }
    }
    zzfree (src, psrc);
  }
  return dst;
}

/*
 *
 * GENERIC BUFFERED WRITE
 *
 */

#define	BUFFSIZE	16777216

char Buff[BUFFSIZE], *rptr = Buff, *wptr = Buff;
int rfd, wfd;
unsigned idx_crc32_complement;

void flushout (void) {
  int w, s;
  if (rptr < wptr) {
    s = wptr - rptr;
    w = write (wfd, rptr, s);
    assert (w == s);
  }
  rptr = wptr = Buff;
}

void clearin (void) {
  rptr = wptr = Buff + BUFFSIZE;
  idx_crc32_complement = -1;
}

void writeout (const void *D, size_t len) {
  idx_crc32_complement = crc32_partial (D, len, idx_crc32_complement);

  const char *d = D;
  while (len > 0) {
    int r = Buff + BUFFSIZE - wptr;
    if (r > len) {
      r = len;
    }
    memcpy (wptr, d, r);
    d += r;
    wptr += r;
    len -= r;
    if (len > 0) {
      flushout ();
    }
  }
}

void *readin (size_t len) {
  assert (len >= 0);
  if (rptr + len <= wptr) {
    return rptr;
  }
  if (wptr < Buff + BUFFSIZE) {
    return 0;
  }
  memcpy (Buff, rptr, wptr - rptr);
  wptr -= rptr - Buff;
  rptr = Buff;
  int r = read (rfd, wptr, Buff + BUFFSIZE - wptr);
  if (r < 0) {
    fprintf (stderr, "error reading file: %m\n");
  } else {
    wptr += r;
  }
  if (rptr + len <= wptr) {
    return rptr;
  } else {
    return 0;
  }
}

void readadv (size_t len) {
  assert (len >= 0 && len <= wptr - rptr);
  idx_crc32_complement = crc32_partial (rptr, len, idx_crc32_complement);
  rptr += len;
}

void bread (void *b, size_t len) {
  void *p = readin (len);
  assert (p != NULL);
  memcpy (b, p, len);
  readadv (len);
  //bytes_read += len;
}

void set_read_file (int read_fd) {
  flushout ();
  clearin ();
  rfd = read_fd;
}

void set_write_file (int write_fd) {
  flushout ();
  clearin ();
  wfd = write_fd;
}

/* returns prime number which greater than 1.5n and not greater than 1.1 * 1.5 * n */
int get_hashtable_size (int n) {
  static const int p[] = {1103,1217,1361,1499,1657,1823,2011,2213,2437,2683,2953,3251,3581,3943,4339,
  4783,5273,5801,6389,7039,7753,8537,9391,10331,11369,12511,13763,15149,16673,18341,20177,22229,
  24469,26921,29629,32603,35869,39461,43411,47777,52561,57829,63617,69991,76991,84691,93169,102497,
  112757,124067,136481,150131,165161,181693,199873,219871,241861,266051,292661,321947,354143, 389561, 428531};
  /*
  471389,518533,570389,627433,690187,759223,835207,918733,1010617,1111687,1222889,1345207,
  1479733,1627723,1790501,1969567,2166529,2383219,2621551,2883733,3172123,3489347,3838283,4222117,
  4644329,5108767,5619667,6181639,6799811,7479803,8227787,9050599,9955697,10951273,12046403,13251047,
  14576161,16033799,17637203,19400929,21341053,23475161,25822679,28404989,31245491,34370053,37807061,
  41587807,45746593,50321261,55353391,60888739,66977621,73675391,81042947,89147249,98061979,107868203,
  118655027,130520531,143572609,157929907,173722907,191095213,210204763,231225257,254347801,279782593,
  307760897,338536987,372390691,409629809,450592801,495652109,545217341,599739083,659713007,725684317,
  798252779,878078057,965885863,1062474559};
  */
  const int lp = sizeof (p) / sizeof (p[0]);
  int a = -1;
  int b = lp;
  n += n >> 1;
  while (b - a > 1) {
    int c = ((a + b) >> 1);
    if (p[c] <= n) { a = c; } else { b = c; }
  }
  if (a < 0) { a++; }
  assert (a < lp-1);
  return p[a];
}

/******************** hashset_ll ********************/
int hashset_ll_init (struct hashset_ll *H, int n) {
  H->size = get_hashtable_size (n);
  H->filled = 0;
  H->n = n;
  H->h = zzmalloc0 (H->size * sizeof(H->h[0]));
  return (H->h != 0);
}

void hashset_ll_free (struct hashset_ll *H) {
  zzfree (H->h, H->size * sizeof(H->h[0]));
  H->h = 0;
  H->size = 0;
  H->filled = 0;
  H->n = 0;
}

int hashset_ll_get (struct hashset_ll *H, long long id) {
  int h1, h2;
  long long D;
  h1 = ((unsigned int) id) % H->size;
  h2 = 1 + ((unsigned int) (id >> 32)) % (H->size - 1);
  while ((D = H->h[h1]) != 0) {
    if (D == id) {
      return 1;
    }
    h1 += h2;
    if (h1 >= H->size) { h1 -= H->size; }
  }
  return 0;
}

int hashset_ll_insert (struct hashset_ll *H, long long id) {
  int h1, h2;
  long long D;
  h1 = ((unsigned int) id) % H->size;
  h2 = 1 + ((unsigned int) (id >> 32)) % (H->size - 1);
  while ((D = H->h[h1]) != 0) {
    if (D == id) {
      return 0;
    }
    h1 += h2;
    if (h1 >= H->size) { h1 -= H->size; }
  }
  H->h[h1] = id;
  H->filled++;
  return 1;
}

/******************** hashset_int ********************/
int hashset_int_init (struct hashset_int *H, int n) {
  H->size = get_hashtable_size (n);
  H->filled = 0;
  H->n = n;
  H->h = zzmalloc0 (H->size * sizeof(H->h[0]));
  return (H->h != 0);
}

void hashset_int_free (struct hashset_int *H) {
  zzfree (H->h, H->size * sizeof(H->h[0]));
  H->h = 0;
  H->size = 0;
  H->filled = 0;
  H->n = 0;
}

int hashset_int_get (struct hashset_int *H, int id) {
  int h1, h2;
  long long D;
  h1 = ((unsigned int) id) % H->size;
  h2 = 1 + ((unsigned int) id) % (H->size - 1);
  while ((D = H->h[h1]) != 0) {
    if (D == id) {
      return 1;
    }
    h1 += h2;
    if (h1 >= H->size) { h1 -= H->size; }
  }
  return 0;
}

int hashset_int_insert (struct hashset_int *H, int id) {
  int h1, h2;
  long long D;
  h1 = ((unsigned int) id) % H->size;
  h2 = 1 + ((unsigned int) id) % (H->size - 1);
  while ((D = H->h[h1]) != 0) {
    if (D == id) {
      return 0;
    }
    h1 += h2;
    if (h1 >= H->size) { h1 -= H->size; }
  }
  H->h[h1] = id;
  H->filled++;
  return 1;
}

int hashmap_ll_int_init (struct hashmap_ll_int *H, int n) {
  H->size = get_hashtable_size (n);
  H->filled = 0;
  H->n = n;
  H->h = zzmalloc0 ((H->size + 1) * sizeof(H->h[0]));
  return (H->h != 0);
}

void hashmap_ll_int_free (struct hashmap_ll_int *H) {
  zzfree (H->h, (H->size + 1) * sizeof(H->h[0]));
  H->h = 0;
  H->size = 0;
  H->filled = 0;
  H->n = 0;
}

int hashmap_ll_int_get (struct hashmap_ll_int *H, long long id, int *p_slot_idx) {
  int h1, h2;
  long long D;
  h1 = ((unsigned int) id) % H->size;
  h2 = 1 + ((unsigned int) (id >> 32)) % (H->size - 1);
  while ((D = H->h[h1].key) != 0) {
    if (D == id) {
      *p_slot_idx = h1;
      return 1;
    }
    h1 += h2;
    if (h1 >= H->size) { h1 -= H->size; }
  }
  *p_slot_idx = h1;
  return 0;
}

int hashmap_int_int_init (struct hashmap_int_int *H, int n) {
  H->size = get_hashtable_size (n);
  H->filled = 0;
  H->n = n;
  H->h = zzmalloc0 ((H->size + 1) * sizeof(H->h[0]));
  return (H->h != 0);
}

void hashmap_int_int_free (struct hashmap_int_int *H) {
  zzfree (H->h, (H->size + 1) * sizeof(H->h[0]));
  H->h = 0;
  H->size = 0;
  H->filled = 0;
  H->n = 0;
}

int hashmap_int_int_get (struct hashmap_int_int *H, int id, int *p_slot_idx) {
  int h1, h2, D;
  h1 = ((unsigned int) id) % H->size;
  h2 = 1 + ((unsigned int) id) % (H->size - 1);
  while ((D = H->h[h1].key) != 0) {
    if (D == id) {
      *p_slot_idx = h1;
      return 1;
    }
    h1 += h2;
    if (h1 >= H->size) { h1 -= H->size; }
  }
  *p_slot_idx = h1;
  return 0;
}
